#include <stdio.h>
#include "Item.h"

void heapsort(Item a[], int l, int r);
void fixDown(Item a[], int k, int N);

int main(int argc, char *argv[]) {
    //
    Item a[] = {'\0', 'A', 'S', 'O', 'R', 'T', 'I', 'N', 'G',
                'E', 'X', 'A', 'M', 'P', 'L', 'E'};

    int i;

    for (i = 1; i <= 15; i++) {
        printf("%c ", a[i]);
    }
    printf("\n");

    heapsort(a, 1, 15);

    for (i = 1; i <= 15; i++) {
        printf("%c ", a[i]);
    }
    printf("\n");

    return 0;
}

/**
 * Program 9.7 Heapsort
 * ----------------------
 * Using `fixDown` directly gives the classical heapsort algorithm.
 * The for loop constructs the heap; then, the while loop exchanges the largest element with the final element
 * in the array and repairs the heap, continuing until the heap is empty.
 * 
 * The pointer pq to a[l-1] allows the code to treat the subarray passed to it as an array
 * with the first element at index 1, for the array representation of the complete tree (see Figure 9.2).
 * Some programming environments may disallow this usage.
 */
void heapsort(Item a[], int l, int r){
    int k;
    int N = r-l+1;
    Item *pq = a + l - 1;

    for(k = N/2; k >= 1; k--){
        fixDown(pq, k, N);
    }

    while (N > 1){
        exch(pq[1], pq[N]);
        fixDown(pq, 1, --N);
    }
    
}

void fixDown(Item a[], int k, int N) {
    int j;
    while (2*k <= N) {
        j = 2 * k;
        if (j < N && less(a[j], a[j+1])) {
            j++;
        }
        if (!less(a[k], a[j])) {
            break;
        }
        exch(a[k], a[j]);
        k = j;
    }
}
